package 真题;/**
 * @author： li
 * @date： 2022-04-07 16:55
 * @version 1.0
 */
import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class 百亿富翁_单调栈 {
//    static ArrayDeque<Integer> ad = new ArrayDeque<>();
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static Stack<Integer> ad = new Stack<>();
    public static void main(String[] args) throws IOException {
        int n =Integer.parseInt(in.readLine());
        int[] l = new int[700005];
        int[] r = new int[700005];
        Arrays.fill(l,-1);
        Arrays.fill(r,-1);
        String[] h =in.readLine().split(" ");
        for(int i=0;i<n;i++){
            while(!ad.isEmpty()&&Integer.parseInt(h[ad.peek()])<=Integer.parseInt(h[i]))
                ad.pop();
            if(!ad.isEmpty())
                l[i]=ad.peek();
            ad.push(i);
        }
        ad.clear();
        for(int i=n-1;i>=0;i--){
            while(!ad.isEmpty()&&Integer.parseInt(h[ad.peek()])<=Integer.parseInt(h[i]))
                ad.pop();
            if(!ad.isEmpty())
                r[i]=ad.peek();
            ad.push(i);
        }
//        out.write("\n");
        for(int i=0;i<n;i++){
            if(l[i]!=-1)
            out.write(l[i]+1+" ");
            else
            out.write(l[i]+" ");
        }
        out.write("\n");
        for(int i=0;i<n;i++){
            if(r[i]!=-1)
            out.write(r[i]+1+ " ");
            else
            out.write(r[i]+ " ");
        }
        out.flush();
    }
}
